package Algorithm;

/**
 * @author yyq
 * @create 2022-01-19 15:14
 *
 * 二分查找算法代码实现
 *
 * 实现:
 *      方式一:递归
 *      方式二:非递归
 *
 * 数组 {1,3, 8, 10, 11, 67, 100}, 编程实现二分查找， 要求使用非递归的方式完成.
 */
public class BinaryLook {
    public static void main(String[] args) {
        int[] array ={1,3, 8, 10, 11, 67, 100};
        if(findWithout(array,3)==-1){
            System.out.println("未查找到数据");
        }else{
            System.out.println(findWithout(array,3));
        }
        find(array,array.length-1,0,3);
    }
    // 递归实现二分查找
    public static void find(int[] a,int high,int low,int val){
        int mid=high+low/2;
        if(mid<0 || mid>high){
            System.out.println("未找到数据");
            return;
        }
        if(a[mid]==val){
            System.out.println(mid);
            return;
        }
        if(a[mid]>val){
            find(a,mid-1,low,val);
        }
        if(a[mid]<val){
            find(a,high,mid+1,val);
        }
    }
    // 非递归实现二分查找
    public static int findWithout(int[] a,int val){
        int high = a.length-1;
        int low = 0;
        int mid = 0;
        while(true){
            mid = high+low/2;
            if(mid<0 || mid>high){
                return -1;
            }
            if(a[mid] == val){
                break;
            }
            if(a[mid]>val){
                high=mid - 1;
                continue;
            }
            if(a[mid]<val){
                low=mid + 1;
                continue;
            }
        }

        return mid;
    }



}
